package 算法.NiuKe.TB;

import 算法.NiuKe.TreeNode;

import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/5/4-15:28
 * @version:1.0
 * @function: 求给定二叉树的最大深度，
 * 最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。
 */
public class NC10 {
    public int maxDepth (TreeNode root) {
        // write code here
        int maxDeep = 0,d = 0;
        Stack<Integer> deep = new Stack<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                d++;
                deep.push(d);
                stack.push(root);
                root = root.left;
            }
            maxDeep = Math.max(maxDeep, deep.peek());
            if (!stack.isEmpty()){
                //  deep = stack.size(); // 当前栈的深度
                root = stack.pop();
                d = deep.pop();
                if (root.right!=null){
                    root= root.right;
                }else {root = null;d = 0;}
            }
        }
        return maxDeep;
    }
}
